package com.ry.day1129;

import java.util.Arrays;

public class LC440 {

    static class Solution {
        /**
         * @param a: an integer array
         * @param v: an integer array
         * @param m: An integer
         * @return: an array
         */
        public int backPackIII(int[] a, int[] v, int m) {
            return shacache(a,v,m);
        }

        public int shacache(int[] a,int[] v,int bag){ //傻缓存
            int n = a.length;
            int[][] dp = new int[n+1][bag+1];
            for (int i = 0; i <=n ; i++) {
                Arrays.fill(dp[i],-1);
            }

            return f1(a,v,0,bag,dp);
        }
        public int f1(int[] a,int[] v,int idx, int rest,int[][] dp){
            if(rest<0) return -1;
            if(idx == a.length) return 0;

            if(dp[idx][rest] !=-1) return dp[idx][rest];

            int ans =0;

            for (int zhang = 0; zhang*a[idx] <=rest ; zhang++) {

                int next = f1(a,v,idx+1,rest-zhang*a[idx],dp);
                if(next!=-1){
                    ans =Math.max(ans, zhang*v[idx]+next);
                }

            }

            dp[idx][rest] =ans;
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.backPackIII(new int[]{2,3,5,7},new int[]{1,5,2,4},10));
        System.out.println(obj.backPackIII(new int[]{1,3,5,7},new int[]{1,5,2,4},10));
    }
}
